use std::ptr;
const LIST_NULL: *mut std::ffi::c_void = ptr::null_mut();
type ListValue = *mut std::ffi::c_void;
#[repr(C)]
struct ListEntry {
    data: ListValue,
    prev: *mut ListEntry,
    next: *mut ListEntry,
}
type ListCompareFunc = fn(ListValue, ListValue) -> i32;
type ListEqualFunc = fn(ListValue, ListValue) -> i32;
#[repr(C)]
struct ListIterator {
    prev_next: *mut *mut ListEntry,
    current: *mut ListEntry,
}
fn list_free(mut list: Option<Box<ListEntry>>) {
    while let Some(mut entry) = list {
        list = entry.next.take();
    }
}
fn list_prepend(list: *mut *mut ListEntry, data: ListValue) -> *mut ListEntry {
    if list.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        let newentry = libc::malloc(std::mem::size_of::<ListEntry>()) as *mut ListEntry;
        if newentry.is_null() {
            return ptr::null_mut();
        }
        (*newentry).data = data;
        if !(*list).is_null() {
            (**list).prev = newentry;
        }
        (*newentry).prev = ptr::null_mut();
        (*newentry).next = *list;
        *list = newentry;
        newentry
    }
}
fn list_append(list: *mut *mut ListEntry, data: ListValue) -> *mut ListEntry {
    if list.is_null() {
        return ptr::null_mut();
    }
    let newentry = unsafe { libc::malloc(std::mem::size_of::<ListEntry>()) as *mut ListEntry };
    if newentry.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*newentry).data = data;
        (*newentry).next = ptr::null_mut();
    }
    if unsafe { *list }.is_null() {
        unsafe {
            *list = newentry;
            (*newentry).prev = ptr::null_mut();
        }
    } else {
        let mut rover = unsafe { *list };
        while unsafe { (*rover).next }.is_not_null() {
            rover = unsafe { (*rover).next };
        }
        unsafe {
            (*newentry).prev = rover;
            (*rover).next = newentry;
        }
    }
    newentry
}
fn list_data(listentry: *mut ListEntry) -> ListValue {
    if listentry.is_null() {
        return LIST_NULL;
    }
    unsafe { (*listentry).data }
}
fn list_set_data(listentry: *mut ListEntry, value: ListValue) {
    if !listentry.is_null() {
        unsafe {
            (*listentry).data = value;
        }
    }
}
fn list_prev(listentry: *mut ListEntry) -> *mut ListEntry {
    if listentry.is_null() {
        std::ptr::null_mut()
    } else {
        unsafe { (*listentry).prev }
    }
}
fn list_next(listentry: *mut ListEntry) -> *mut ListEntry {
    if listentry.is_null() {
        return std::ptr::null_mut();
    }
    unsafe { (*listentry).next }
}
fn list_nth_entry(list: *mut ListEntry, n: u32) -> *mut ListEntry {
    let mut entry = list;
    for _ in 0..n {
        if entry.is_null() {
            return std::ptr::null_mut();
        }
        unsafe {
            entry = (*entry).next;
        }
    }
    entry
}
fn list_nth_data(list: *mut ListEntry, n: u32) -> ListValue {
    let entry = list_nth_entry(list, n);
    if entry.is_null() {
        LIST_NULL
    } else {
        unsafe { (*entry).data }
    }
}
fn list_length(list: *mut ListEntry) -> u32 {
    let mut entry = list;
    let mut length = 0;
    while !entry.is_null() {
        length += 1;
        entry = unsafe { (*entry).next };
    }
    length
}
fn list_to_array(list: *mut ListEntry) -> *mut ListValue {
    unsafe {
        let length = list_length(list) as usize;
        let array = libc::malloc(std::mem::size_of::<ListValue>() * length) as *mut ListValue;
        if array.is_null() {
            return std::ptr::null_mut();
        }
        let mut rover = list;
        for i in 0..length {
            if !rover.is_null() {
                *array.add(i) = (*rover).data;
                rover = (*rover).next;
            }
        }
        array
    }
}
fn list_remove_entry(list: *mut *mut ListEntry, entry: *mut ListEntry) -> i32 {
    unsafe {
        if list.is_null() || (*list).is_null() || entry.is_null() {
            return 0;
        }
        if (*entry).prev.is_none() {
            *list = (*entry).next.unwrap_or(std::ptr::null_mut());
            if let Some(next) = (*entry).next {
                (*next).prev = None;
            }
        } else {
            if let Some(prev) = (*entry).prev {
                (*prev).next = (*entry).next;
            }
            if let Some(next) = (*entry).next {
                (*next).prev = (*entry).prev;
            }
        }
        libc::free(entry as *mut _);
        1
    }
}
fn list_remove_data(list: *mut *mut ListEntry, callback: ListEqualFunc, data: ListValue) -> u32 {
    let mut entries_removed = 0;
    let mut rover = unsafe { *list };
    while !rover.is_null() {
        let next = unsafe { (*rover).next };
        if callback(unsafe { (*rover).data }, data) != 0 {
            if unsafe { (*rover).prev }.is_null() {
                unsafe { *list = (*rover).next };
            } else {
                unsafe { (*(*rover).prev).next = (*rover).next };
            }
            if !unsafe { (*rover).next }.is_null() {
                unsafe { (*(*rover).next).prev = (*rover).prev };
            }
            unsafe { libc::free(rover as *mut libc::c_void) };
            entries_removed += 1;
        }
        rover = next;
    }
    entries_removed
}
fn list_sort_internal(list: *mut *mut ListEntry, compare_func: ListCompareFunc) -> *mut ListEntry {
    unsafe {
        let mut pivot: *mut ListEntry;
        let mut rover: *mut ListEntry;
        let mut less_list: *mut ListEntry = std::ptr::null_mut();
        let mut more_list: *mut ListEntry = std::ptr::null_mut();
        let mut less_list_end: *mut ListEntry;
        let mut more_list_end: *mut ListEntry;
        if list.is_null() || compare_func.is_none() {
            return std::ptr::null_mut();
        }
        if (*list).is_null() || (**list).next.is_null() {
            return *list;
        }
        pivot = *list;
        rover = (**list).next;
        while !rover.is_null() {
            let next = (*rover).next;
            if compare_func((*rover).data, (*pivot).data) < 0 {
                (*rover).prev = std::ptr::null_mut();
                (*rover).next = less_list;
                if !less_list.is_null() {
                    (*less_list).prev = rover;
                }
                less_list = rover;
            } else {
                (*rover).prev = std::ptr::null_mut();
                (*rover).next = more_list;
                if !more_list.is_null() {
                    (*more_list).prev = rover;
                }
                more_list = rover;
            }
            rover = next;
        }
        less_list_end = list_sort_internal(&mut less_list, compare_func);
        more_list_end = list_sort_internal(&mut more_list, compare_func);
        *list = less_list;
        if less_list.is_null() {
            (*pivot).prev = std::ptr::null_mut();
            *list = pivot;
        } else {
            (*pivot).prev = less_list_end;
            (*less_list_end).next = pivot;
        }
        (*pivot).next = more_list;
        if !more_list.is_null() {
            (*more_list).prev = pivot;
        }
        if more_list.is_null() {
            return pivot;
        } else {
            return more_list_end;
        }
    }
}
fn list_sort(list: *mut *mut ListEntry, compare_func: ListCompareFunc) {
    list_sort_internal(list, compare_func);
}
fn list_find_data(
    list: *mut ListEntry,
    callback: ListEqualFunc,
    data: ListValue,
) -> *mut ListEntry {
    let mut rover = list;
    while !rover.is_null() {
        unsafe {
            if callback((*rover).data, data) != 0 {
                return rover;
            }
            rover = (*rover).next;
        }
    }
    std::ptr::null_mut()
}
fn list_iterate(list: *mut *mut ListEntry, iter: &mut ListIterator) {
    iter.prev_next = list;
    iter.current = std::ptr::null_mut();
}
fn list_iter_has_more(iter: *mut ListIterator) -> i32 {
    unsafe {
        if (*iter).current.is_null() || (*iter).current != *(*iter).prev_next {
            (*(*iter).prev_next).is_null() as i32
        } else {
            !(*(*iter).current).next.is_null() as i32
        }
    }
}
fn list_iter_next(iter: &mut ListIterator) -> ListValue {
    if iter.current.is_null() || iter.current != *iter.prev_next {
        iter.current = *iter.prev_next;
    } else {
        iter.prev_next = &mut (*iter.current).next;
        iter.current = (*iter.current).next;
    }
    if iter.current.is_null() {
        LIST_NULL
    } else {
        (*iter.current).data
    }
}
fn list_iter_remove(iter: &mut ListIterator) {
    unsafe {
        if iter.current.is_null() || iter.current != *iter.prev_next {
        } else {
            *iter.prev_next = (*iter.current).next;
            if !(*iter.current).next.is_null() {
                (*(*iter.current).next).prev = (*iter.current).prev;
            }
            libc::free(iter.current as *mut libc::c_void);
            iter.current = std::ptr::null_mut();
        }
    }
}
